\section{Theoretical Analysis of Optimal Path-Tree Construction}
\label{theory}

In this section, 
we investigate several theoretical questions related to path-tree cover construction. 
We show that given the path-decomposition of DAG $G$, finding the optimal path-tree cover of $G$ is equivalent to the problem of finding the {\em maximum spanning tree} of a directed graph. 
We demonstrate that the optimal tree cover by Agrawal {\em et. al} ~\cite{SIGMOD:AgrawalBJ:1989} is a special case of our problem. In addition, we show that our path-tree cover can always achieve better compression than any chain cover and tree cover. 
%Along these lines, we show several heuristics for both path-decomposition and finding the good path-tree cover of DAG $G$. 

To achieve this, we utilize the predecessor set of each vertex. 
But first we note that the computational cost for computing of all the predecessor sets of a 
given DAG $G$ is equivalent to the cost of the transitive closure of $G$, with $O(nm)$ time complexity. 
Thus it may not be applicable to very large graphs as its computational cost would be prohibitive.  It can, however, still be utilized as a starting point for understanding the potentials of path-tree cover and its study may help to develop better heuristics to efficiently extract a good path-tree cover. 
In addition, these algorithms might be better suited for other applications if the knowledge of predecessor sets is readily available. Thus, they can be applied to compress the transitive closure. 

\comment{
The first question is how to find the optimal path-tree construction which can optimize the compression of the transitive closure. 
We provide an optimal algorithm,  which utilizes the knowledge of the predecessor set of each vertex and assumes the path decomposition is given, will guarantee to find the best tree cover to minimize the compression of the transitive closure. 
We also investigate alternative path-decomposition methods. 
We show that both chain decomposition approach ~\cite{} and tree cover ~\cite{} can be utilized in our algorithm, and thus we establish the results that our path-tree construction can beat the best tree cover.
In Section~\ref{experiment}, we will show path-tree can significantly improve the compression rate based on the tree cover approach. 
%We further illustrate some cases where path-tree perform significantly better than tree cover. 
}

\subsection{Optimal Path-Tree Cover with \\
Path-Decomposition}
\label{OPTC}
We first consider the following restricted version of the optimal path-tree cover problem.

\noindent{\bf Optimal Path-Tree Cover (OPTC) Problem:}
{\em 
Let $P=(P_1,\cdots,P_k)$ be a path-decomposition of DAG $G$. 
And let ${\mathcal G_s(P)}$ be the family including all the path tree covers of $G$ which are based on $P$.
The OPTC problem tries to find the optimal tree cover $G[T] \in {\mathcal G_s(P)}$, 
such that it requires minimal index size to compress the transitive closure of $G$. }

To solve this problem, let us first analyze the index size which will be needed to compress the transitive closure utilizing a path-tree $G[T]$. 
Note that $R^c(u)$ is the compressed set of vertices which vertex $u$ can reach and for compression purposes, $R^c(u)$ does not include $v$ if 1) $u$ can reach $v$ through the path-tree $G[T]$ and 2) there is an vertex $x \in R^c(u)$, such that $x$ can reach $v$ through the path-tree $G[T]$. 
Given this, we can define the compressed index size as 
\[Index\_cost=\sum_{u \in V(G)} |R^c(u)|\]
(We omit the labeling cost for each vertex as it is the same for all path-trees.)
To optimize the index size, we utilize the following equivalence. 

\blemma
\label{equivalent}
For any vertex $v$, let $T(v)$ be the immediate predecessor of $v$ on the path-tree $G(T)$. Then, we have 
\[Index\_cost=\sum_{v \in V(G)} |S(v) \backslash (\bigcup_{x \in T(v)} (S(x)\cup \{x\}))|\]
where $S(v)$ includes all the vertices which can reach vertex $v$.   
\elemma
\bproof
For vertex $v$, if $v \in R^c(u)$, then any path starting from $u$ and reaching $v$ will not include a vertex $w$, such that $u$ reaches $w$ and $w$ reaches $v$ through the path-tree. 
We claim that such vertex $u \in S(v) \backslash (\bigcup_{x \in T(v)} (S(x)\cup \{x\}))$.
This can be proved by contradition. 
Suppose $u$ reaches $v$ and $u \in \cup_{x \in T(v)} (S(x)\cup \{x\})$. 
Then, we have $u \rightarrow x \rightarrow v$ ($u$ reaches $x$ and $x$ is the immediate predecessor of $v$ and thus, $x$ dominates $v$ through the path-tree.)
Thus, for each vertex \[v \in R^c(u) \Longleftrightarrow u \in S(v) \backslash (\cup_{x \in T(v)} (S(x)\cup \{x\}))\]    
\eproof

Given this, we can solve the OPTC problem by utilizing the predecessor sets to assign weight to the edges on the directed path-graph in Subsection~\ref{step3}. 
Thus, the path-tree which corresponds to the maximum spanning tree of the path-graph optimizes the index size for the transitive closure. 
Consider we have two paths $P_i$, $P_j$ and the minimal equivalent edge set $E^R_{P_i,P_j}$. 
For each edge $(u,v)\in E^R_{P_i,P_j}$, let $v^\prime$ be the vertex which is the immediate predecessor of $v$ in path $P_j$. 
Then, we define the predecessor set of $v$ with respect to $u$ as \[S_u(v)=(S(u)\cup \{u\}) \backslash (S(v^\prime) \cup \{v^\prime\})\]
If $v$ is the first vertex in the path $P_j$, then we define $S(v^\prime)=\emptyset$. 
Given this, we define the weight from path $P_i$ to path $P_j$ as
\[w_{P_i,P_j}=\sum_{(u,v)\in E^R_{P_i,P_j}} |S_{u}(v)|\]
We refer to such criteria as {\em OptIndex}. 
 
\bthm
\label{optimal}
The path-tree cover corresponding to the maximum spanning tree from the directed weighted path-graph defined by the OptIndex achieves the minimal index size for the compressed transitive closure among all the path-trees in ${\mathcal G_s(P)}$. 
\ethm
\bproof 
We decompose $Index\_cost$ utilizing the path-decomposition $P=P_1 \cup \cdots \cup \cdots P_k$ as follows:
\[Index\_cost=\sum_{1\leq i \leq k} \sum_{v\in P_i} |S(v) \backslash (\cup_{x \in T(v)} (S(x)\cup \{x\}))| \]
Note that $S(v) \supseteq (\cup_{x \in T(v)} (S(x)\cup \{x\}))$. 
Then, to minimize the $Index\_cost$, it is equivalent to maximize
\[\sum_{1\leq i \leq k} \sum_{v\in P_i} |\cup_{x \in T(v)} (S(x)\cup \{x\})|\]
We can further rewrite it as  ($u_i$ is the last vertex in the path $P_i$)
\[\sum_{1\leq i \leq k} ((\sum_{v\in P_i\backslash\{u_i\}} |S(v)\cup \{x\}|
+\sum_{(u,v)\in E^R_{P_i,P_j}} |S_u(v)|)\]
where $P_j$ is the parent path in the path-tree of path $P_i$.  
Since the first half of the sum is the same for the given path decomposition, we essentially need to maximize 
\[\sum_{1\leq i \leq k} \sum_{(u,v)\in E^R_{P_i,P_j}} |S_u(v)| = \sum_{1\leq i \leq k} w_{P_i,P_j}\]
\eproof

Recall that in Agrawal's optimal tree cover algorithm~\cite{SIGMOD:AgrawalBJ:1989}, to build the tree, for each vertex $v$ in DAG $G$, they essentially choose its immediate predecessor $u$ with the maximal number of predecessors as its parent vertex, i.e., 
\[|S(u)| \geq |s(x)|, \forall x\in in(v), u\in in(v)\]
Given this, we can easily see that if the path decomposition treats each vertex in $G$ as an individual path, then we have the optimal tree cover algorithm from Agrawal {\em et al.}~\cite{SIGMOD:AgrawalBJ:1989}. 
 
\bthm 
The optimal tree cover algorithm ~\cite{SIGMOD:AgrawalBJ:1989} is a special case of path-tree construction when each vertex corresponds to an individual path and the weighted directed path-graph utilizes the {\em OptIndex} criteria.
\ethm
\bproof 
Note that for any vertex $u$ and $v$ and if $(u,v)\in E(G)$, then
the weight on the directed edge $(u,v)$ (each path is a single vertex) 
is $w_{u,v}=|S(u)\cup\{u\}|$. 
\eproof

\subsection{Optimal Path-Decomposition}
\label{opd}

Theorem~\ref{optimal} shows the optimal path-tree cover for the given path-decomposition. 
A follow-up question is then how to choose the path-decomposition which can achieve overall optimality. 
This problem, however, remains open at this point (undecided between $P$ and $NP$). 
Instead, we ask the following question. 

\noindent{\bf Optimal Path-Decomposition (OPD) Problem:}
{\em Assuming we will utilize only the path-decomposition to compress the transitive closure (in other words, no cross-path edges), the OPD problem is to find the optimal \\
path-decomposition which can maximally compress the transitive closure.}

Note that there are clearly cases, where the optimal path-decomposition does not lead to the complete path-tree cover.
This nevertheless provides a good heuristic to choose a good path-decomposition in the case where the predecessor sets are available. 
Note that the OPD problem is different from the chain decomposition problem in~\cite{Jagadish90}, where the goal is to find the minimal width of the chain decomposition. 

We map this problem to the {\em minimal-cost maximum-flow} problem~\cite{Goldber90}. 
We transform the given DAG $G$ into a network $G_N$ (referred to as the flow-network for $G$) as follows.  
First, each vertex $v$ in $G$ is split into two vertices $s_v$ and $e_v$ 
and we use a single edge connecting $s_v$ to $e_v$. 
We assign the cost of such an edge $F(s_v,e_v)$ to be $0$.  
Then, for an edge $(u,v)$ in $G$, we map it to $(e_u,s_v)$ in $G_N$. 
The cost of such an edge is $F(e_u,s_v)=-|S(u)\cup \{u\}|$, where $S(u)$ is the predecessor set of $u$.  
Finally, we add a virtual source vertex and a virtual sink vertex.
The virtual source vertex is connected to any vertex $s_v$ in $G_N$ with cost $0$. 
Similarly, each vertex $e_v$ is connected to the sink vertex with cost being zero. 
The capacity of each edge in $G_N$ is one ($C(x,y)=1$). 
Thus, each such edge can take maximally one unit of flow, and correspondingly each vertex can belong to one and only one path. 

Let $c(x,y)$ be the amount of flow over edge $(x,y)$ in $G_N$. 
The cost of such a flow over the edge is $c(x,y)\cdotp F(x,y)$, where $c(x,y)\leq C(x,y)$. 
We would like to find a flow which goes through all the vertex-edges $(s_v,e_v)$ and whose overall cost is minimal. 
We can solve it using an algorithm for the {\em minimum-cost maximum-flow} problem which can solve the case where the amount of flow being sent from the source to the sink is given. 
Let $i$-flow be the solution for the minimum-cost maximum-flow problem when the total amount of flow from the source to the sink is fixed at $i$ units. 
We can then vary the amount of flow from $1$ to $n$ units and choose the one $i$-flow which achieves the minimum cost. 
%The total cost of this procedure is $O(n^4)$. 

\bthm
\label{optimalflow}
Let $G_N$ be the flow-network for DAG $G$. 
Let $F_k$ be the minimal cost of the amount of $k$-flow from the source to the sink, $1\leq k \leq n$. 
Let $i$-flow from the source to the sink minimize all the $n$-flow, 
$F_i \leq F_k, 1 \leq k \leq n$. 
The $i$-flow corresponds to the best index size if we utilize only the path-decomposition to compress the transitive closure. 
\ethm

\bproof
First, we can prove that for any given amount $i$ flow, where $i$ is an integer, the flow with minimal-cost will pass each edge either with $1$ or $0$ (similar to the Integer Flow property~\cite{CORMEN90}). 
Basically, the flow can be treated as a binary flow. 
In other words, any flow going from the the source to the sink will not split into branches (note that each edge has only capacity one).
Thus, applying Lemma~\ref{optimal}, we can see that the total cost of the flow (multiplied by negative one) corresponds to the savings for the {\em Index\_cost}  
\[\sum_{1\leq i \leq k} ((\sum_{v\in P_i\backslash\{u_i\}} |S(v)\cup \{x\}|
=\sum_{(u,v)\in G_N} c(u,v) \times F(u,v)\]
where $u_i$ is the last vertex in path $P_i$. 
Then, let $i$-flow be the one which achieves minimal-cost (the most negative cost) from the source to the sink. 
Thus, when we invoke the algorithm which solves the minimal-cost maximal-flow for a given amount of flow $i$, we will achieve the minimal cost which will be less than any other $j$-flow, $i\neq j$. 
Thus, we identify the flow and find our path-decomposition. 
\eproof

Note that there are several algorithms which can solve the minimal-cost maximal-flow problem with different time complexities. Interested readers can refer to~\cite{Goldber90} for more details. Our methods can utilize any of these algorithms. 

\subsection{Optimality of Path-Tree Cover Approach} 
In the following, we consider how to build a path-tree which utilizes the existing chain-decomposition or tree-cover (if they are already computed) to achieve better compression results. 
Note that both chain-decomposition and tree-cover approaches are generally as expensive as the computation of transitive closure. 

A major difference between chain-decomposition and path-decomposition is that each path $P_i$ in the path-decomposition is a subgraph of $G$. 
However, a chain may not be a subgraph of $G$. It is a subgraph of the transitive closure. 
Therefore, several methods developed by Jagadish actually require the knowledge of transitive closure~\cite{Jagadish90}.
We can easily apply any chain decomposition into our path-tree framework as follows. 
For any chain $C_i=(v_1,\cdots, v_k)$, if $(v_i,v_{i+1})$ is not an edge in $G$, then we add $(v_i,v_{i+1})$ into the edge set $E(G)$. 
The resulting graph $G^\prime$ has the same transitive closure of $G$. 
Now, the chain decomposition of $G$ becomes a path decomposition of $G^\prime$ and we can then apply the path-tree construction based on this decomposition. 

Clearly, the path-tree built upon $C$ will achieve better compression than the corresponding chain decomposition (at least one cross-path edge can be utilized to compress the transitive closure, see the formula in Lemma~\ref{optimal}) if there is any edge connecting two chains in $C$ in DAG $G$. 
Note that if there are no edges connecting two chains in $G$, then both path-tree and chain decomposition completely represent $G$ and thus maximally compress $G$.   

\input{Figures/Tree2Path.tex}

For any tree cover, we can also transform it into path-decomposition using Algorithm~\ref{alg:tree2path}. 
Essentially, we extract the first path by the shortest path from its root to one of its leaves. 
After we remove the path, the tree will then break into several subtrees. 
We perform the same extraction for each subtree until each subtree is empty. 
Thus, we can have the path-decomposition based on the tree cover.
In addition, we note that there is at most one edge link two paths extracted from Algorithm~\ref{alg:tree2path}. 

Given this, we can prove the following theorem. 
\bthm
For any tree cover, the path-tree cover which uses the path-decomposition from the tree cover and is built by OptIndex has an index size lower than or equal to the index size of the corresponding tree cover.    
\ethm
\bproof
This follows Lemma~\ref{optimal}. 
Further, there is a path-tree cover which can represent the same shape as the original tree cover, i.e., if there is an edge in the original tree cover link from path $P_i$ to $P_j$, there is a path-tree that can preserve its path-path relationship by only adding more edges (from DAG $G$, if exists) from $P_i$ to $P_j$. 
\eproof


\subsection{Optimal Query Processing}
\label{intrevalquery}
Here we describe a better query processing procedure algorithm with $O(log ^2k)$ cost.
We first build an interval tree based on the intervals of each vertex
in $R(u)$ as follows (this is slightly different from~\cite{Berg00}):
Let $x_{mid}$ be the median of the end points of the intervals. Let
$u.P[1]$ and $u.P[2]$ be the first starting point and ending point of
the interval $u.P$, respectively.  We define the interval tree
recursively. The root node $v$ of the tree stores $x_{mid}$, such that
\beqnarr
I_{left} &=&\{u|u.P[2]<x_{mid} \} \nonumber \\
I_{mid} &=&\{u|x_{mid} \in u.P \} \nonumber \\
I_{right}&=&\{u|u.P[1]> x_{mid} \} \nonumber \eeqnarr

Then, the left subtree of $v$ is an interval tree for the set of
$I_{left}$ and the right subtree of $v$ is an interval tree for the
set of $I_{right}$.  We store $I_{mid}$ only once and order it by
$u.X$ (the $X$ label of the vertices in $I_{mid}$). This is the key
difference between our interval tree and the standard one from~\cite{Berg00}.
In addition, when $I=\emptyset$, the interval tree is
a leaf.  Following ~\cite{Berg00}, we can easily construct in
$O(klogk)$ time an interval tree using $O(k)$ storage and depth $O(log
k)$.

\input{Figures/Query.tex}

The query procedure using this interval tree is shown in
Algorithm~\ref{alg:query} when $u$ does not reach $v$ using only the
path-tree.  The complexity of the algorithm is $O(log^2k)$.  The
correctness of the Algorithm~\ref{alg:query} can be proved as follows.

\blemma For the case where $u$ cannot reach $v$ using only the
path-tree, then Algorithm~\ref{alg:query} correctly answer the
reachability query.  \elemma


\bproof The key property is that for any two vertices $w$ and
$w^\prime$ in $I_{mid}$, either $w.P \subseteq w^\prime.P$ or
$w^\prime.P \subseteq w.P$.  This is because the intervals are
extracted from the tree structure, and it is easy to see that:
\[w.P \cap w^\prime.P \neq \emptyset \Rightarrow (w.P \subseteq w^\prime.P) \vee (w^\prime.P \subseteq w.P) \]
Thus, we can order the intervals based on the inclusion relationship.
Further, if $ w.P \subseteq w^\prime.P$, then we have $w.X <
w^\prime.X$ (Otherwise, we can drop $w.P$ if $w.X > w^\prime.X$).
Following this, we can see that if any $w$ from Line 4, such that $w.X
\leq v.X$ and if $w.P$ does not include $v.P$, then no other vertex in
the $I_{mid}$ can include $v.P$ with $w.X \leq v.X$.  \eproof





\comment{  
Note that the major advantage of the path-tree cover compared with the traditional tree cover is that allows in-degree to be two, while the tree cover require each node has only one-incoming edge. Thus, the path-tree cover can efficiently and naturally handle the grid type of DAG. 
Maximally, the path-tree cover can allow almost $2n$ edges where the the tree cover can cover only around $n-1$ edges of the DAG. 
}






%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: 
